package com.zklh.leetcode.structure.stack;

/**
 * 二叉堆算法实现
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/7/26 22:33
 */
public class MaxPQ<K extends Comparable<K>> {

    private K[] pq;

    private int length;

    public MaxPQ(int cap) {

        pq = (K[]) new Comparable[cap+1];
        length = 0;
    }

    public K delMax(){
        if (length == 0) {
            return null;
        }
        K delE = pq[1];

        swap(1, length);
        length -= 1;
        pq[length] = null;
        sink(1);
        return delE;
    }

    public void insert(K e){
        if (length == pq.length-1) {
            return;
        }
        length++;
        pq[length] = e;
        swim(length);
    }

    // 上浮元素, 使用该函数的基础是只有i这个节点有问题, 其他节点都满足最大堆要求
    private void swim(int i) {
        while (i != 1 && less(i/2, i)) {
            swap(i/2, i);
            i = i/2;
        }
    }

    // 下沉元素使用该函数的基础是只有i这个节点有问题, 其他节点都满足最大堆要求
    private void sink(int i) {
        while (2 * i <= pq.length-1) {
            int maxChild = 2 * i;
            if (2 * i + 1 <= pq.length - 1 && less(2 * i, 2 * i + 1)) {
                maxChild = 2 * i + 1;
            }
            if (less(maxChild, i)) {
                break;
            }
            swap(i, maxChild);
            i = maxChild;
        }
    }

    // 交换两个元素
    private void swap(int i1, int i2) {
        K temp = pq[i1];
        pq[i1] = pq[i2];
        pq[i2] = temp;
    }


    private boolean less(int i1, int i2) {
        return pq[i1].compareTo(pq[i2]) < 0;
    }

}
